package com.nanbei.divideandconqure;

import java.util.Random;

/**
 * @ClassDescription:  数组中第K大的元素  数组中的元素由大到小排序（分而治之）
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/11 15:58
 */
public class KthLargestElementInAnArray {

    public static void main(String[] args) {
        System.out.println(findKthLargest(new int[]{3,2,1,5,6,4},2));
    }

    public static int findKthLargest(int[] nums, int k) {
        return findK(nums,0,nums.length-1, nums.length-k);
    }

    public static int findK(int[]nums ,int left,int right,int k){

        int i = querySort(nums, left, right);
        if (k ==i){
            return nums[i];
        }
        if (i >k){
           return findK(nums, left, i - 1,k);
        }else{
           return findK(nums, i + 1, right,k);
        }
    }

    private static int querySort(int[] nums, int left, int right) {
        Random random = new Random();
        int nextInt = random.nextInt(right - left + 1);
        int index = nextInt + left;
        // 交换随机的基准坐标和最左侧的元素
        swap(nums,index,left);
        int max = right;
        int min = left+1;
        int pv = nums[left];
        while (min <= max) {

            // 从右向左找 小于等于 基准点的
            while (min <= max && nums[max] > pv) {
                max--;
            }

            // 从左向右找 大于等于 基准点的
            while (min <= max && nums[min] < pv) {
                min++;
            }

            // 找到后交换位置
            if (min <= max){
                swap(nums, max, min);
                min++;
                max--;
            }

        }
        swap(nums, left, max);
        return max;
    }

    public static void swap(int[] nums , int i, int j){
        int num = nums[i];
        nums[i] = nums[j];
        nums[j] = num;
    }
}
